package leetcode.code0437;

import leetcode.helper.tree.TreeNode;

public class Solution extends Solution437 {

	private int ans;

	@Override
	public int pathSum(TreeNode root, int sum) {
		ans = 0;
		path(root, sum);
		return ans;
	}

	public int path(TreeNode root, int sum) {
		if (root == null)
			return 0;
		Sum(root, sum);
		path(root.left, sum);
		path(root.right, sum);
		return ans;
	}

	public void Sum(TreeNode root, int sum) {
		if (root == null)
			return;
		sum -= root.val;
		ans += sum == 0 ? 1 : 0;
		Sum(root.left, sum);
		Sum(root.right, sum);
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();// bug
		so.debug4();// bug
		so.debug5();// bug
		so.debug6();
		so.debug7();
		so.debug8();
		so.debug9();
		so.debug10();
	}

}
